class ListNode{
		int val;
		ListNode next;
		public ListNode(int x){
			val = x;
			next = null;
		}
}
public class ReorderList {

	/**
	 * @param args
	 */
	 
	public static ListNode reorderList(ListNode head) {
		ListNode pre = null;
        ListNode current =null;
        
        int index = 0;
        ListNode fast = head;
        ListNode slow = head;
		while (fast != null && fast.next != null && fast.next.next!= null)
		{
			//System.out.println(fast.val);
			fast = fast.next.next;
			slow = slow.next;
			
		}

		ListNode first = head;
		ListNode second = slow.next;
		slow.next = null;
		second = reverseList(second);
		while(second != null)
		{
			ListNode temp1 =first.next;
			ListNode temp2 = second.next;
			first.next = second;
			second.next = temp1;
			first = temp1;
			second = temp2;
		}
		return head;
	}
	static ListNode reverseList(ListNode head)
	{
		if(head == null || head.next == null)
			return head;
		ListNode pre = head;
		ListNode cru = head.next;
		while(cru != null){
		ListNode temp = cru.next;
		cru.next = pre;
		pre = cru;
		cru = temp;
		}
		head.next = null;
		return pre;
	}
	static void printListNode(ListNode head)
	{
		while(head != null)
		{
			System.out.print(head.val+"->");
			head = head.next;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		ListNode node5 = new ListNode(5);
		ListNode node6 = new ListNode(6);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node1 = ReorderList.reorderList(node1);
		
		printListNode(node1);
	}
	
}
